package gti310.tp3.solver;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

import gti310.tp3.GraphHolder;
import gti310.tp3.Solutions;

public class ConcreteSolver implements Solver<Object, Object> {

	private Solutions solution = new Solutions();
	private GraphHolder graph;
	private List<Integer> solList = new ArrayList<Integer>();
	private List<Integer> verticleCollection = new ArrayList<Integer>();
	private int firstVerticle;

	@Override
	public Object solve(Object input) {
		this.graph = (GraphHolder) input;
		firstVerticle = this.graph.startingVerticle;
		solve(graph.startingVerticle - 1, -1, buildMatrix());
		return this.solution;
	}

	// As the name suggest... it builds the matrix.
	// It also populate the verticleCollection used during solving
	private String[][] buildMatrix() {
		String[][] matrix = new String[this.graph.verticleNb][this.graph.verticleNb];
		ListIterator<String[]> verticle = this.graph.verticleList
				.listIterator();
		String[] value;

		// Populate verticleCollection
		for (int x = 0; x < this.graph.verticleNb; x++) {
			this.verticleCollection.add(x);
		}

		// Populate the matrix
		while (verticle.hasNext()) {
			value = verticle.next();
			matrix[Integer.parseInt(value[0]) - 1][Integer.parseInt(value[1]) - 1] = value[2];
		}
		return matrix;
	}

	// Recursively called to find every path that goes into every verticles.
	// -1 if previousVerticle doesn't exist
	private void solve(int startingVerticle, int previousVerticle,
			String[][] matrix) {
		this.solList.add(startingVerticle);
		for (int i = 0; i < matrix.length; i++) {
			if (matrix[startingVerticle][i] != null) {
				if (i == firstVerticle - 1 && i != previousVerticle
						&& this.solList.containsAll(this.verticleCollection)) {
					// Solution found
					this.solList.add(firstVerticle - 1);
					this.solution.add(this.solList);
					this.solList.remove(this.solList.size() - 1);
				}
				if (i != previousVerticle && !this.solList.contains(i)) {
					// We don't want to return to the same verticle.
					solve(i, startingVerticle, matrix);
					this.solList.remove(this.solList.size() - 1);

				}

			}

		}

	}

}
